§ 2.1 Field of the Invention
The present invention concerns communicating information in a mobile ad hoc network. More specifically, the present invention concerns determining a state of a node in an ad hoc network, determining a topological state of the ad hoc network and/or using the determined node and network topology states to route (e.g., forward) communications to a destination node.
§ 2.2 Related Art
The present invention may be used in a mobile ad hoc network environment. Although mobile ad hoc networks are known to those skilled in the art, they are introduced in § 2.2.1 for the reader's convenience. Then, § 2.2.2 introduces known network architectures and routing protocols, as well as disadvantages and limitations of such known architectures and protocols as perceived by the inventors. Finally, § 2.2.3 introduces needs that have not been met by such known architectures and protocols.
§ 2.2.1 Mobile Ad Hoc Networks
As introduced above, the present invention may operate in the environment of a mobile ad hoc network. A mobile ad hoc network is a self-organizing and rapidly deployable network in which neither a wired backbone nor a centralized control is needed. Thus, a mobile ad hoc network is adaptable to the highly dynamic topology resulting from the mobility of network nodes and changing propagation conditions. The nodes of a mobile ad hoc network may communicate with one another over scarce wireless channels in a multi-hop manner. Thus, in addition to performing transmission and reception functions, the mobile nodes may perform a routing (e.g., data or message forwarding) function.
Having introduced mobile ad hoc networks, known network architectures and routing protocols are introduced in § 2.2.2 below.
§ 2.2.2 Network Architectures and Routing Protocols
Since the routing protocol to be used in an ad hoc network is typically affected by the network architecture, various network architectures are introduced first in § 2.2.2.1 below. There are two (2) basic categories of network architectures—flat and hierarchical. Each is introduced below.
§ 2.2.2.1 An Overview of Known Network Architectures Used in Mobile Ad HOC Networks
In hierarchical network architectures (See, e.g., the hierarchical spine routing protocol discussed in the articles: B. Das and V. Bharghavan, “Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets,” IEEE ICC'97, June 1997; and B. Das, R. Sivakumar and V. Bharghavan, “Routing in Ad Hoc Networks Using a Virtual Backbone,” IEEE IC3N'97, September 1997, pp. 1–20.), details of the network topology are concealed by aggregating nodes into clusters, aggregating clusters into superclusters, and so on (See, e.g., the article [4] G. S. Lauer, “Packet-Radio Routing,” M. E. Steenstrup, editors, Routing in Communications Networks, Prentice-Hall, 1995, pp. 375–379.). Some nodes serve as “cluster heads” and “gateway nodes”. In this way, control messages may only have to be propagated within a cluster. Thus, such hierarchical architectures are advantageous in that they reduce the storage requirements and communications overhead in large wireless networks. However, the cluster head nodes and gateway nodes have a greater computation and communication burden than other nodes. This complicates mobility management. Further, by concentrating critical functions at cluster head nodes and gateway nodes, network reliability can be greatly affected by the reliability of a few critical nodes. The failure of such nodes can lead to catastrophic failure of the network.
In flat network architectures, all nodes carry the same responsibilities. Thus, such architectures avoid catastrophic failures and spread computational and storage burdens more fairly. Unfortunately, however, flat network architectures use bandwidth resources inefficiently since control messages are propagated globally, throughout the network. This limits the scalability of flat network architectures.
Having introduced the basic types of network architectures which may be used in a mobile ad hoc network, various routing protocols which may be used in a mobile ad hoc network are introduced in § 2.2.2.2 below.
§ 2.2.2.2 An Overview of Known Routing Protocols and Schemes Used in Mobile Ad Hoc Networks
There are two (2) basic categories of routing protocols—proactive versus reactive. Each is introduced below.
In proactive routing schemes, nodes continuously maintain complete routing information of the network. In this way, when a node needs to forward a packet, the route is available ahead of time (hence the term “proactive”). This scheme therefore avoids delays that would otherwise occur in searching for a route. Unfortunately, however, in highly dynamic (i.e., rapidly changing) network topologies, proactive routing schemes require a significant amount of scarce wireless communications resources (or bandwidth) to maintain current and complete routing information.
Proactive protocols such as the link state routing protocol (also referred to as “open shortest path first”) (See, e.g., the article, R. Perlman, Interconnections: Bridges and Routers, Addison-Wesley, 1992, pp. 149–152 and pp. 205–233.) and the distance vector routing protocol (also referred to as “Bellman-Ford”) (See, e.g., the article, R. Perlman, Interconnections: Bridges and Routers, Addison-Wesley, 1992, pp. 149–152 and pp. 205–233.) were not designed to work in mobile networks (See, e.g., the article, J. P. Macker and M. S. Corson, “Mobile Ad Hoc Networking and the IETF,” ACM Mobile Comput. and Commun. Rev., Vol. 2, No. 1, January 1998, pp. 9–14.) The inventors believe that these protocols do not converge fast enough for networks having a rapidly changing topology. Other distance vector routing protocols, such as the destination-sequenced distance vector routing protocol (See, e.g., the article, C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” ACM Comput. Commun. Rev., Vol. 24, No. 4, (ACM SIGCOMM'94) October 1994, pp. 234–244.) and the wireless routing protocol (See, e.g., the article, S. Murthy and J. J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” ACM Mobile Networks and Applications J., Vol. 1, No. 2, 1996, pp. 183–197.) were proposed to eliminate counting to infinity and looping problems of the distributed Bellman-Ford algorithm.
In reactive schemes, nodes only maintain routes to active destinations. A route search is needed for every new destination. Examples of reactive protocols include the ad hoc on demand distance vector routing protocol (See, e.g., the article, C. E. Perkins, “Ad Hoc On Demand Distance Vector (AODV) Routing,” Internet Draft, November 1997.), the temporally-ordered routing algorithm (See, e.g., the article, V. D. Park and M. S. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,” IEEE INFOCOM'97, Kobe, Japan, April 1997.) and the dynamic source routing protocol (See, e.g., the article, D. B. Johnson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” T. Imielinski and H. Korth, editors, Mobile Computing, Kluwer, 1996.). Although communication/overhead is reduced when reactive schemes are used instead of proactive schemes, unfortunately, communications are delayed due to route searching. Also, an active route may be broken, causing the need for a subsequent route search. This problem is exacerbated in networks having rapidly changing topologies.
Some routing protocols or schemes are basically hybrids of the proactive and reactive schemes. One example of such a hybrid routing protocol is referred to as the zone routing protocol (or “ZRP”) (See, e.g., the articles: M. R. Pearlman and Z. J. Haas, “The Performance of the Zone Routing Protocol in Reconfigurable Wireless Networks,” IEEE J. Select. Areas Commun., Vol. 17, No. 8, August 1999, pp. 1395–1414; Z. J. Haas and M. R. Pearlman, “The Performance of Query Control Scheme for the Zone Routing Protocol,” ACM SIGCOMM'98, Vancouver, Canada, 1998; and Z. J. Haas, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks,” Internet Draft, November 1997.).
Other ad hoc routing protocols have been discussed (See, e.g., the articles: M. Gerla and J. T. Tsai, “Multicluster, Mobile, Multimedia Radio Network,” ACM Wireless Networks, Vol. 1, No. 3, 1995, pp. 255–265; D. J. Baker, A. Ephremides and J. A. Flynn, “The Design and Simulation of a Mobile Radio Network with Distributed Control,” IEEE J. Select. Areas Commun., Vol. SAC-2, No. 1, January 1984, pp. 226–237; A. Ephremides, J. E. Wieselthier and D. J. Baker, “A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signaling,” Proc. IEEE, Vol. 75, No. 1, January 1987, pp. 56–73; and J. Sharony, “An Architecture for Mobile Radio Networks with Dynamically Changing Topology Using Virtual Subnets,” ACM Mobile Networks and Applications J., Vol. 1, No. 1, 1996, pp. 75–86.).
In the zone routing protocol (ZRP), each node proactively maintains the topological information within its routing zone (e.g., within a predefined distance) only. Thus, the zone routing protocol (ZRP) is proactive within a zone. For routing outside a node's routing zone, the zone routing protocol (ZRP) employs “bordercasting”. “Bordercasting” exploits the structure of the routing zone by allowing a node to send messages to nodes on the boundary of its routing zone (such nodes may be referred to as “peripheral nodes”) and by preventing non-peripheral nodes from accessing the messages. Routes are efficiently discovered by bordercasting a route query to all the source's peripheral nodes. These peripheral nodes, in turn, bordercast the query to their peripheral nodes if the destination node is not within the respective routing zones of the peripheral nodes, and so on. Once the destination node is found, a route reply is echoed back to the source node. Thus, the zone routing protocol (ZRP) is reactive with respect to destination nodes beyond a source node's zone. The routing path, which includes a list of peripheral nodes between the source and destination nodes, is stored in the header of a packet(s) or cached in the queried peripheral nodes. Unfortunately, any change in the peripheral nodes gives rise to the need to discover another route.
Other articles of interest may include: L. Kleinrock and F. Kamoun, “Hierarchical Routing for Large Networks: Performance Evaluation and Optimization,” Computer Networks, Vol. 1, No. 3, 1977, pp. 155–174; J. Behrens and J. J. Garcia-Luna-Aceves, “Hierarchical Routing Using Link Vectors,” IEEE INFOCOM'98, San Francisco, Calif., March 1998; UCLA Parallel Computing Lab, Maisie User Manual Release 2.2, December 1995; J. Short, R. Bagrodia, L. Kleinrock, “Mobile Wireless Network System Simulation,” Proc. ACM Mobile Commun. Network. Conf., Berkeley, Calif., November 1995; and M. Joa-Ng, “Routing Protocol and Medium Access Protocol for Mobile Ad Hoc Networks,” Ph.D. dissertation, Department of Electrical Engineering, Polytechnic University, Brooklyn, 1999.
§ 2.2.3 Unmet Needs
In view of the foregoing, there is a need for an improved routing protocol for used in ad hoc networks. The routing protocol should use less bandwidth than purely proactive routing schemes, should provide faster route determination that purely reactive routing schemes, and should better adapt to changing network topology as well as incur less location search overhead than hybrid routing schemes.